#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "queue"

using namespace std;
/*HJJ QQ479287006
 *输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

 

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
//TODO 忘了我擦
int quickSort(vector<int> &arr, int low, int high) {
    int p = arr[low];

    while (low < high) {
        while (low < high && arr[high] >= p)high--;
        arr[low] = arr[high];

        while (low < high && arr[low] <= p)low++;
        arr[high] = arr[low];
    }

    arr[low] = p;
    return low;

}

vector<int> ret;

void quickSearch(vector<int> &arr, int lo, int hi, int k) {
    if (k < 0)
        return;

    int j = quickSort(arr, lo, hi);


    if (j == k) {
        //直接获取左边的数据就行 卧槽啊 为什么左边已经排序好了  todo
        // 这个并不是这个快拍的特点应该是这个递归的原因
        for (int i = 0; i <= k; ++i) {
            ret[i] = arr[i];
        }


    } else if (j > k) {

        quickSearch(arr, lo, j - 1, k);

    } else if (j < k) {

        quickSearch(arr, j + 1, hi, k);
    }

}

vector<int> getLeastNumbers(vector<int> &arr, int k) {

    ret.resize(k);

    quickSearch(arr, 0, arr.size() - 1, k - 1);

    return ret;
}


/*
 *
 * 优先对列和堆有什么区别呢？
这里面说的堆默认我们最常使用的二叉堆，而二叉堆只是优先队列的一种是实现方式而已。那么优先队列还有哪些实现方式呢？
还有：二项堆 平衡树 线段树 甚至用二进制分组的vector来实现一个优先对列。
所以说 优先队列和堆不是一个同level的概念 如果非要说 他们之间的关系就是：二叉堆只是优先队列的一种实现方式，而java的PriorityQueue也是基于这个实现的。
 *TODO
 *
 * */
vector<int> getLeastNumbers1(vector<int> &arr, int k) {
    if (k == 0) return vector<int>();
    priority_queue<int, less<int>> q;

    for (int &a : arr) {
        if (q.size() < k) {
            q.push(a);
        } else {
            if (q.top() <= a) continue;
            else {
                q.pop();
                q.push(a);
            }
        }
    }

    vector<int> res;
    while (!q.empty()) {
        res.push_back(q.top());
        q.pop();
    }
    return res;
}